/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  //创建一个状态数组dp：dp[i]表示组成组成整数i所需的最少完全平方数的个数
  const dp = new Array(n + 1).fill(Infinity)
  //初始化dp[0]为0：组成整数0需要0个完全平方数
  dp[0] = 0

  //状态转移方程：dp[i] = Math.min(dp[i] , dp[i - j*j] + 1), 对于所有 j，使得 j*j <= i
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
    }
  }

  //返回结果
  return dp[n]
};